package dfs;

import javax.swing.tree.TreeNode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {

     public class ListNode {
         int val;
         ListNode next;
         ListNode(int val) { this.val = val; }
         ListNode(int val, ListNode next) { this.val = val; this.next = next; }
         ListNode() {}
     }
    /**
     * 合并两个有序的链表
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) {
            return list2;
        }
        if(list2 == null) {
            return list1;
        }
        if(list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }


    /**
     * 反转链表
     */
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;

        return newHead;
    }

    /**
     * 两两交换链表中的节点
     */
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode tmp = swapPairs(head.next.next);
        ListNode ret = head.next;
        ret.next = head;
        head.next = tmp;
        return ret;
    }

    /**
     *  Pow(x, n)
     * @param x
     * @param n
     * @return
     */
    public double myPow(double x, int n) {
        return n > 0 ? pow(x, n) : 1.0 / pow(x, -n);
    }
    public double pow(double x, int n) {
        if( n == 0) {
            return 1.0;
        }
        double tmp = pow(x, n/2);
        return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    /**
     * 2331. 计算布尔二叉树的值
     */
    public boolean evaluateTree(TreeNode root) {
        if(root.left == null) return root.val == 0 ? false : true;

        boolean left = evaluateTree(root.left);
        boolean right = evaluateTree(root.right);
        return root.val == 2 ? left | right : left & right;
    }

    /**
     * 129. 求根节点到叶节点数字之和
     */
    public int sumNumbers(TreeNode root) {
        return dfs(root,0);
    }
    public int dfs(TreeNode root, int preSum) {
        preSum = preSum * 10 + root.val;
        if(root.left == null && root.right == null) {
            return preSum;
        }
        int ret = 0;
        if(root.left != null) {
            ret += dfs(root.left, preSum);
        }
        if(root.right != null) {
            ret += dfs(root.right, preSum);
        }
        return ret;
    }

    /**
     * 814. 二叉树剪枝
     */
    public TreeNode pruneTree(TreeNode root) {
        if(root == null) return null;

        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);

        if(root.left == null && root.right == null && root.val == 0) {
            root = null;
        }
        return root;
    }

    /**
     * 98. 验证二叉搜索树
     */
    long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;

        boolean left = isValidBST(root.left);

        boolean cur = false;
        if(prev < root.val) {
            cur = true;
        }

        if(cur == false) return false;
        prev = root.val;
        boolean right = isValidBST(root.right);


        return left && right && cur;
    }

    /**
     * 230. 二叉搜索树中第K小的元素
     */
    int count;
    int ret;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        dfs(root);
        return ret;

    }
    void dfs(TreeNode root) {
        if(root == null || count == 0) return;

        dfs(root.left);
        count--;
        if(count == 0) {
            ret = root.val;
            return;
        }
        dfs(root.right);
    }

    /**
     * 257. 二叉树的所有路径
     */

    List<String> ret1;
    public List<String> binaryTreePaths(TreeNode root) {
        ret1 = new ArrayList<>();
        StringBuffer path;
        dfs2(root, new StringBuffer());
        return ret1;
    }
    public void dfs2(TreeNode root, StringBuffer _path) {
        StringBuffer path = new StringBuffer(_path);
        path.append(Integer.toString(root.val));
        if(root.left == null && root.right == null) {
            ret1.add(path.toString());
            return;
        }
        path.append("->");
        if(root.left != null) dfs2(root.left, path);
        if(root.right != null) dfs2(root.right, path);
    }


    /**
     * 46. 全排列
     */
    List<List<Integer>> ret3;
    List<Integer> path2;
    boolean[] check;
    public List<List<Integer>> permute(int[] nums) {
        ret3 = new ArrayList<>();
        path2 = new ArrayList<>();
        check = new boolean[nums.length];

        dfs3(nums);
        return ret3;
    }
    public void dfs3(int[] nums) {
        if(nums.length == path2.size()) {
            ret3.add(new ArrayList<>(path2));
            return;
        }
        for(int i = 0; i < nums.length; i++) {
            if(check[i] == false) {
                path2.add(nums[i]);
                check[i] = true;

                dfs3(nums);
                //回溯
                check[i] = false;
                path2.remove(path2.size()-1);
            }
        }
    }


    /**
     * 78. 子集
     */
    List<Integer> path4;
    List<List<Integer>> ret4;
    public List<List<Integer>> subsets(int[] nums) {
        path4 = new ArrayList<>();
        ret4 = new ArrayList<>();

        dfs4(nums, 0);

        return ret4;
    }

    public void dfs4(int[] nums, int pos) {
        if(pos == nums.length) {
            ret4.add(new ArrayList<>(path4));
            return;
        }
        // 选
        path4.add(nums[pos]);
        dfs4(nums, pos + 1);
        path4.remove(path4.size() - 1);// 恢复现场

        // 不选
        dfs4(nums, pos + 1);

    }
    //解法二
    List<Integer> path5;
    List<List<Integer>> ret5;
    public List<List<Integer>> subsets2(int[] nums) {
        path5 = new ArrayList<>();
        ret5 = new ArrayList<>();

        dfs5(nums, 0);

        return ret5;
    }

    public void dfs5(int[] nums, int pos) {
        ret5.add(new ArrayList<>(path5));

        for(int i = pos; i < nums.length; i++) {
            path5.add(nums[i]);
            dfs5(nums, i + 1);
            path5.remove(path5.size()-1);// 恢复现场
        }

    }


    /**
     * 1863. 找出所有子集的异或总和再求和
     */
    int sum;
    int path;
    public int subsetXORSum(int[] nums) {
        dfs(nums, 0);
        return sum;
    }
    public void dfs(int[] nums, int pos) {
        sum += path;
        for(int i = pos; i < nums.length; i++) {
            path ^= nums[i];
            dfs(nums, i + 1);
            path ^= nums[i]; // 恢复现场

        }
    }

    /**
     * 47. 全排列 II
     */
    List<Integer> path6;
    List<List<Integer>> ret6;
    boolean[] check6;
    public List<List<Integer>> permuteUnique(int[] nums) {
        path6 = new ArrayList<>();
        ret6 = new ArrayList<>();
        check6 = new boolean[nums.length];

        Arrays.sort(nums);

        dfs6(nums, 0);

        return ret6;
    }
    public void dfs6(int[] nums, int pos) {
        if(pos == nums.length) {
            ret6.add(new ArrayList<>(path6));
            return;
        }
        for(int i = 0; i < nums.length; i++) {
            // 剪枝
            if(check6[i] == true || (i != 0 && nums[i] == nums[i-1] && check6[i-1] == false)) {
                continue;
            }
            path6.add(nums[i]);
            check6[i] = true;
            dfs6(nums, pos + 1);

            // 回溯
            path6.remove(path6.size() - 1);
            check6[i] = false;
        }
    }


    /**
     * 17. 电话号码的字母组合
     */
    String[] hash = {"","", "abc", "def", "ghi", "jkl","mno", "pqrs", "tuv", "wxyz"};
    List<String> ret7;
    StringBuffer path7;
    public List<String> letterCombinations(String digits) {
        ret7 = new ArrayList<>();
        path7 = new StringBuffer();

        if(digits.length() == 0) return ret7;

        dfs7(digits, 0);
        return ret7;
    }
    public void dfs7(String digits, int pos) {
        if(pos == digits.length()) {
            ret7.add(path7.toString());
            return;
        }

        String cur = hash[digits.charAt(pos) - '0'];
        for(int i = 0; i < cur.length(); i++) {
            path7.append(cur.charAt(i));
            dfs7(digits, pos + 1);
            // 回溯
            path7.deleteCharAt(path7.length() - 1);

        }
    }

    /**
     * 22. 括号生成
     */
    int left;
    int right;
    int N;
    StringBuffer path8;
    List<String> ret8;
    public List<String> generateParenthesis(int n) {
        N = n;
        ret8 = new ArrayList<>();
        path8 = new StringBuffer();
        dfs8();
        return ret8;
    }
    public void dfs8() {
        if(right == N) {
            ret8.add(path8.toString());
            return;
        }
        if(left < N) { // 添加左括号
            path8.append('(');
            left++;
            dfs8();
            // 恢复现场
            path8.deleteCharAt(path8.length() - 1);
            left--;
        }
        if(left > right) { // 添加右括号
            path8.append(')');
            right++;
            dfs8();
            path8.deleteCharAt(path8.length() - 1);
            right--;
        }

    }

    /**
     * 77. 组合
     */
    List<Integer> path9;
    List<List<Integer>> ret9;
    int n, k;
    public List<List<Integer>> combine(int _n, int _k) {
        path9 = new ArrayList<>();
        ret9 = new ArrayList<>();
        n = _n;
        k = _k;
        dfs9(1);
        return ret9;
    }
    public void dfs9(int pos) {
        if(path9.size() == k) {
            ret9.add(new ArrayList<>(path9));
            return;
        }

        for(int i = pos; i <= n; i++) {
            path9.add(i);
            dfs9(i + 1);
            // 恢复现场
            path9.remove(path9.size() - 1);
        }
    }

    /**
     * 494. 目标和
     */
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int sum = 0;
        for(int x : nums) sum += x;
        int a = (target  + sum) / 2;
        if(a < 0 || (sum + target) % 2 != 0) return 0;
        // 1. 创建 dp 表
        // dp[i][j]表示：从前i个数中选，总和正好等于j,一共有多少种选法
        int[] dp = new int[a+1];
        // 2. 初始化
        dp[0] = 1;
        // 3. 填表
        for(int i = 1; i <= n; i++) {
            for(int j = a; j >= nums[i-1]; j--) {
                dp[j] += dp[j-nums[i-1]];
            }
        }
        // 4. 返回值
        return dp[a];
    }

    int ret10;
    int path10;
    int aim;
    public int findTargetSumWays2(int[] nums, int target) {
        aim = target;
        dfs10(nums, 0);
        return ret10;
    }
    public void dfs10(int[] nums, int pos) {
        if(pos == nums.length) {
            if(path10 == aim) {
                ret10++;
            }
            return;
        }
        // 加法
        path10 += nums[pos];
        dfs10(nums, pos + 1);
        path10 -= nums[pos];

        // 减法
        path10 -= nums[pos];
        dfs10(nums, pos + 1);
        path10 += nums[pos];

    }

    int ret11;
    int aim11;
    public int findTargetSumWays3(int[] nums, int target) {
        aim = target;
        dfs11(nums, 0, 0);
        return ret;
    }
    public void dfs11(int[] nums, int pos, int path) {
        if(pos == nums.length) {
            if(path == aim) {
                ret++;
            }
            return;
        }
        // 加法
        dfs11(nums, pos + 1, path + nums[pos]);

        // 减法
        dfs11(nums, pos + 1, path - nums[pos]);


    }

    /**
     * 39. 组合总和
     */
    List<List<Integer>> ret12;
    List<Integer> path12;
    int aim12;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        ret12 = new ArrayList<>();
        path12 = new ArrayList<>();
        aim12 = target;
        dfs12(candidates, 0, 0);
        return ret12;

    }
    public void dfs12(int[] nums, int pos, int sum) {
        if(sum == aim12) {
            ret12.add(new ArrayList<>(path));
            return;
        }
        if(sum > aim12 || pos == nums.length) return;
        for(int i = pos; i < nums.length; i++) {
            path12.add(nums[i]);
            dfs12(nums, i, sum + nums[i]);
            path12.remove(path12.size() - 1);
        }
    }
    List<List<Integer>> ret13;
    List<Integer> path13;
    int aim13;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        ret13 = new ArrayList<>();
        path13 = new ArrayList<>();
        aim13 = target;
        dfs13(candidates, 0, 0);
        return ret13;

    }
    public void dfs13(int[] nums, int pos, int sum) {
        if(sum == aim13) {
            ret13.add(new ArrayList<>(path13));
            return;
        }

        if(sum > aim13 || pos == nums.length) return;
        for(int k = 0; k * nums[pos] + sum <= aim13; k++) {
            if(k != 0) {

                path13.add(nums[pos]);
            }
            dfs13(nums, pos + 1, sum + k * nums[pos]);
        }
        for(int k = 1; k * nums[pos] + sum <= aim; k++) {
            path13.remove(path13.size() - 1);
        }


    }

    /**
     * 784. 字母大小写全排列
     */
    StringBuffer path14;
    List<String> ret14;
    public List<String> letterCasePermutation(String s) {
        path14 = new StringBuffer();
        ret14 = new ArrayList<>();

        dfs14(s, 0);
        return ret14;
    }
    public void dfs14(String s, int pos) {
        if(pos == s.length()) {
            ret14.add(path14.toString());
            return;
        }
        char ch = s.charAt(pos);
        path14.append(ch);
        dfs14(s, pos + 1);
        path14.deleteCharAt(path14.length() - 1);

        if(ch < '0' || ch > '9') {
            char tmp = change(ch);
            path14.append(tmp);
            dfs14(s, pos + 1);
            path14.deleteCharAt(path14.length() - 1);
        }
    }
    public char change(char ch) {
        if(ch >= 'a' && ch <= 'z') {
            return ch -= 32;
        }else {
            return ch += 32;
        }

    }


    /**
     * 526. 优美的排列
     */
    boolean[] check15;
    int ret15;
    public int countArrangement(int n) {
        check15 = new boolean[n + 1];

        dfs15(1, n);
        return ret15;
    }
    public void dfs15(int pos, int n) {
        if(pos == n + 1) {
            ret15++;
            return;
        }
        for(int i = 1; i <= n; i++) {
            if(check15[i] == false && (i % pos == 0 || pos % i == 0)) {
                check15[i] = true;
                dfs15(pos + 1, n);
                check15[i] = false;
            }
        }
    }

    /**
     * 51. N 皇后
     */
    boolean[] checkCol, checkDig1, checkDig2;
    List<List<String>> ret16;
    char[][] path16;
    int n16;
    public List<List<String>> solveNQueens(int _n) {
        n16 = _n;
        checkCol = new boolean[n16];
        checkDig1 = new boolean[n16 * 2];
        checkDig2 = new boolean[n16 * 2];
        ret16 = new ArrayList<>();
        path16 = new char[n16][n16];
        for(int i = 0; i < n16; i++) {
            Arrays.fill(path16[i], '.');
        }
        dfs16(0);
        return ret16;
    }
    public void dfs16(int row) {
        if(row == n16) {
            List<String> tmp = new ArrayList<>();
            for(int i = 0; i < n16; i++) {
                tmp.add(new String(path16[i]));
            }
            ret16.add(new ArrayList<>(tmp));
        }
        for(int col = 0; col < n16; col++) {
            if(checkCol[col] == false && checkDig1[row - col + n16] == false && checkDig2[row + col] == false) {
                path16[row][col] = 'Q';
                checkCol[col] = checkDig1[row - col + n16] = checkDig2[row + col] = true;
                dfs16(row + 1);
                path16[row][col] = '.';
                checkCol[col] = checkDig1[row - col + n16] = checkDig2[row + col] = false;
            }
        }

    }


    /**
     * 36. 有效的数独
     */
    boolean[][] row, col;
    boolean[][][] grid;
    public void solveSudoku(char[][] board)
    {
        row = new boolean[9][10];
        col = new boolean[9][10];
        grid = new boolean[3][3][10];
        // 初始化
        for(int i = 0; i < 9; i++)
            for(int j = 0; j < 9; j++)
                if(board[i][j] != '.')
                {
                    int num = board[i][j] - '0';
                    row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
                }

        dfs(board);
    }
    public boolean dfs(char[][] board)
    {
        for(int i = 0; i < 9; i++)
        {
            for(int j = 0; j < 9; j++)
            {
                if(board[i][j] == '.')
                {
                    // 填数
                    for(int num = 1; num <= 9; num++)
                    {
                        // 剪枝
                        if(!row[i][num] && !col[j][num] && !grid[i / 3][j / 3]
                                [num])
                        {
                            board[i][j] = (char)('0' + num);
                            row[i][num] = col[j][num] = grid[i / 3][j / 3]
                                    [num] = true;
                            if(dfs(board) == true) return true; // 重点理解
                            // 恢复现场
                            board[i][j] = '.';
                            row[i][num] = col[j][num] = grid[i / 3][j / 3]
                                    [num] = false;
                        }
                    }
                    return false; // 重点理解
                }
            }
        }
        return true; // 重点理解
    }
    /**
     * 37. 解数独
     */



}
